11195. Бормотание в стаде (Бронза)

Малоизвестен тот факт, что у коров свой алфавит “cowphabet”. Он состоит из тех же 26 букв от ‘a’ до ‘z’, но в другом порядке. Чтобы скоротать время, Беси бормочет cowphabet опять и опять. Фермеру Джону интересно, сколько раз она его пробормотала.

По заданной строке букв, которые ФД расслышал из бормотания Беси, определите минимальное количество раз, которое Беси должна пробормотать cowphabet, чтобы ФД услышал заданную строку. ФД не всегда обращает внимание на бормотание Беси, поэтому он может не расслышать некоторые буквы из бормотания Беси. Данная Вам строка содержит только те буквы, которые он услышал.

Вход. Первая строка содержит 26 маленьких латинских букв от ‘a’ до ‘z’ в порядке их появления в cowphabet. Следующая строка содержит строку из маленьких латинских букв, которые услышал ФД. Эта строка имеет длину от 1 до 1000.

Выход. Выведите минимальное количество раз, которое Беси пробормотала алфавит.

Пример входа	Пример выхода
abcdefghijklmnopqrstuvwxyz mood	3

РЕШЕНИЕ

строки

Анализ алгоритма

Пусть alph содержит алфавит, s содержит строку, которую пробормотала Беси. Будем передвигаться по буквам строки s, каждый раз находя ее в алфавите alph: по строке алфавита двигаемся слева направо столько раз, сколько потребуется для обнаружения всех букв из s.

Пример

В примере cowphabet упорядочен как нормальный алфавит. Бесси пробормотала cowphabet как минимум 3 раза. Ниже показано, как Беси бормотала, большими буквами выделены те, которые услышал ФД.

Реализация алгоритма

Читаем алфавит alph и строку s.

cin >> alph;

cin >> s;

Количество проходов по алфавиту подсчитываем в переменной cnt.

cnt = 0;

Переменной i проходим по буквам слова s.

for (i = 0; i < s.size(); )

{

Переменной j проходим по алфавиту. Как только в алфавите встретится буква s[i], увеличиваем i на 1.

for (j = 0; j < alph.size(); j++)

if (s[i] == alph[j]) i++;

cnt++;

}

Выводим ответ.

cout << cnt << endl;